package com.bing.java.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 
 * 快排的时间复杂度达到了 O(n²)，但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。
 * 
 * @author bing
 *
 *         2019年11月11日 下午1:56:21
 * 
 *         算法思想： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
 *         然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
public class SortFast {

	public static void main(String[] args) {
		int [] a = {5,3,12,8,7};
		quickSort1(a, 0, a.length-1);
		quickSort2(a, 0, a.length-1);

		System.out.println("排序后的数组：" + Arrays.toString(a));

	}

	/**
	 * 快速排序方法1
	 * 
	 * @param arr
	 * @param low
	 * @param high
	 */
	public static void quickSort1(int arr[], int low, int high) {
		int start = low;
		int end = high;
		int key = arr[low];

		while (end > start) {
			// 从后往前比较
			while (end > start && arr[end] >= key) {
				// 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
				end--;
			}
			if (arr[end] <= key) {
				int temp = arr[end];
				arr[end] = arr[start];
				arr[start] = temp;
			}
			// 从前往后比较
			while (end > start && arr[start] <= key) {
				// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
				start++;
			}
			if (arr[start] >= key) {
				int temp = arr[start];
				arr[start] = arr[end];
				arr[end] = temp;
			}
			// 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
		}

		// 递归
		if (start > low) {
			quickSort1(arr, low, start - 1);// 左边序列。第一个索引位置到关键值索引-1
		}
		if (end < high) {
			quickSort1(arr, end + 1, high);// 右边序列。从关键值索引+1到最后一个
		}
	}
	
	
	/**
	 * 快速排序方法2
	 * 
	 * @param arr
	 * @param low
	 * @param high
	 */
	public static int[] quickSort2(int[] array, int start, int end) {
		if (array.length < 1 || start < 0 || end >= array.length || start > end)
			return null;
		int smallIndex = partition(array, start, end);
		if (smallIndex > start)
			quickSort2(array, start, smallIndex - 1);
		if (smallIndex < end)
			quickSort2(array, smallIndex + 1, end);
		return array;
	}
 
	/**
	 * 快速排序算法——partition
	 */
	public static int partition(int[] array, int start, int end) {
		int pivot = (int) (start + Math.random() * (end - start + 1));
		int smallIndex = start - 1;
		swap(array, pivot, end);
		for (int i = start; i <= end; i++)
			if (array[i] <= array[end]) {
				smallIndex++;
				if (i > smallIndex)
					swap(array, i, smallIndex);
			}
		return smallIndex;
	}
 
	/**
	 * 交换数组内两个元素
	 */
	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
